package stackandqueue

import "strconv"

// RemoveDuplicates removes repeat nerbor characters
// .e.g RemoveDuplicates("abbaca") => "ca"
func RemoveDuplicates(s string) string {
	stack := NewStack()
	for _, c := range s {
		if stack.IsEmpty() {
			stack.Push(c)
		} else {
			top := stack.Pop().(rune)
			if top != c {
				stack.Push(top)
				stack.Push(c)
			}
		}
	}
	if !stack.IsEmpty() {
		var result []rune
		for !stack.IsEmpty() {
			result = append(result, stack.Pop().(rune))
		}
		for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
			result[i], result[j] = result[j], result[i]
		}
		return string(result)
	}
	return ""
}

// IsValidParentheses returns true if the input string is valid parentheses
// .e.g IsValidParentheses("()") => true
// .e.g IsValidParentheses("()[]{}") => true
func IsValidParentheses(s string) bool {
	stack := NewStack()
	for _, c := range s {
		if c == '(' || c == '[' || c == '{' {
			stack.Push(c)
		} else {
			if stack.IsEmpty() {
				return false
			}
			top := stack.Pop().(rune)
			if c == ')' && top != '(' {
				return false
			}
			if c == ']' && top != '[' {
				return false
			}
			if c == '}' && top != '{' {
				return false
			}
		}
	}
	return stack.IsEmpty()
}

// evalRPN
func evalRPN(tokens []string) int {
	stack := NewStack()
	for _, token := range tokens {
		if token == "+" || token == "-" || token == "*" || token == "/" {
			aStr := stack.Pop().(string)
			bStr := stack.Pop().(string)
			a, _ := strconv.Atoi(aStr)
			b, _ := strconv.Atoi(bStr)
			switch token {
			case "+":
				stack.Push(strconv.Itoa(a + b))
			case "-":
				stack.Push(strconv.Itoa(a - b))
			case "*":
				stack.Push(strconv.Itoa(a * b))
			case "/":
				stack.Push(strconv.Itoa(a / b))
			}
		} else {
			stack.Push((token))
		}
	}
	return stack.Pop().(int)

}

// NewStack creates a new stack
func NewStack() *Stack {
	return &Stack{}
}

// Stack struct
type Stack struct {
	data []interface{}
}

// Push pushes an element to the stack
func (s *Stack) Push(v interface{}) {
	s.data = append(s.data, v)
}

// Pop pops an element from the stack
func (s *Stack) Pop() interface{} {
	if s.IsEmpty() {
		return nil
	}
	v := s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	return v
}

// IsEmpty returns true if the stack is empty
func (s *Stack) IsEmpty() bool {
	return len(s.data) == 0
}

// MyQueue struct
type MyQueue struct {
	Stack []int
}
